
//1631.最小体力消耗路径
class Solution {
public:
    int minimumEffortPath(vector<vector<int>>& heights) {
        int n = heights.size(),m = heights[0].size();
        int dx[] = {0,0,1,-1}; 
        int dy[] = {1,-1,0,0};

        priority_queue<tuple<int,int,int>,vector<tuple<int,int,int>>,greater<tuple<int,int,int>>> pq;
        vector<vector<int>> dis(n,vector<int>(m,INT_MAX));      //记录每个坐标的最短路径
        vector<vector<int>> vist(n,vector<int>(m));             //记录已经确定最小路径的位置
        pq.push({0,0,0});
        vist[0][0] = 1;
        while(pq.size())
        {
            auto [phy,x,y] = pq.top();
            pq.pop();
            if(phy >= dis[x][y]) continue;
            dis[x][y] = phy;
            vist[x][y] = 1;
            for(int k = 0 ; k < 4; k++)
            {
                int a = x+dx[k],b = y + dy[k];
                if(a < 0 || a >= n || b < 0 ||b >= m) continue;     //下一个位置越界了
                int hgt = abs(heights[x][y] - heights[a][b]);       //求下一个位置与当前位置的高度差
                if(!vist[a][b] ) pq.push({max(hgt,phy),a,b});       //选择下一个位置和原来位置中高度差的较大值插入队列
            }
        }            
        return dis[n-1][m-1];
    }
};